Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list.
The new list should be made by splicing together the nodes of the first two lists.

题目大意：合并2个有序链表为一个新的链表，返回新链表头指针，要求不能新创建链表，合并只能在原链表上执行

题目难度：Easy

/**
 * Created by gzdaijie on 16/5/8
 * 将最后的结果存在l1中
 * l1.val < l2.val 则l1继续前行
 * 否则将l2的当前节点插入l1当前节点之前
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head;
        ListNode p = new ListNode(0);
        p.next = l1;
        head = p;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p = p.next;
                l1 = l1.next;
            } else {
                p = p.next = l2;
                l2 = l2.next;
                p.next = l1;
            }
        }
        if (l2 != null) {
            p.next = l2;
        }
        return head.next;
    }
}